﻿using System.Collections.Generic;

namespace DependencyAnalysis.Algorithms.SubstringDetection
{
    //TODO test classes, refactor
    public class SuffixTree
    {
        private readonly char[] _text;
        private int _nodeCount;

        public char[] Text
        {
            get { return _text; }
        }

        private readonly Node _root;

        public Node RootNode
        {
            get { return _root; }
        }

        public SuffixTree(char[] text)
        {
            _text = text;
            _root = new Node(this, null);

            Suffix suffixLink = new Suffix(_root, 0, -1);
            for (int i = 0; i < text.Length; i++)
            {
                AddPrefix(suffixLink, i);
            }
        }

        public int CreateNewNodeNumber()
        {
            return _nodeCount++;
        }

        private void AddPrefix(Suffix suffixLink, int endIndex)
        {
            Node lastParentNode = null;
            Node parentNode;

            while (true)
            {
                parentNode = suffixLink.OriginNode;

                if (FindMatchingEdge(suffixLink, endIndex, ref parentNode)) break;

                // We didn't find a matching edge, so we create a new one, add it to the tree at the parent node position,
                // and insert it into the hash table.  When we create a new node, it also means we need to create
                // a suffix link to the new node from the last node we visited.
                lastParentNode = CreateNewEdge(endIndex, parentNode, lastParentNode);

                // This final step is where we move to the next smaller suffix
                if (Equals(suffixLink.OriginNode, _root))
                    suffixLink.BeginIndex++;
                else
                    suffixLink.ChangeOriginNode();
                suffixLink.Canonize();
            }
            UpdateSuffixNode(lastParentNode, parentNode);
            suffixLink.EndIndex++; //Now the endpoint is the next active point
            suffixLink.Canonize();
        }

        private Node CreateNewEdge(int endIndex, Node parentNode, Node lastParentNode)
        {
            Edge newEdge = new Edge(endIndex, _text.Length - 1, parentNode);
            newEdge.Insert();
            UpdateSuffixNode(lastParentNode, parentNode);
            lastParentNode = parentNode;
            return lastParentNode;
        }

        private bool FindMatchingEdge(Suffix suffixLink, int endIndex, ref Node parentNode)
        {
            Edge edge;
            if (suffixLink.IsExplicit())
            {
                //RULE1
                edge = suffixLink.OriginNode.FindEdge(_text[endIndex]);
                if (edge != null)
                    return true;
            }
            else
            {
                //implicit node, a little more complicated
                edge = suffixLink.OriginNode.FindEdge(_text[suffixLink.BeginIndex]);
                int span = suffixLink.GetSpan();
                //RULE3
                if (_text[edge.BeginIndex + span + 1] == _text[endIndex])
                    return true;
                //RULE2
                parentNode = edge.SplitEdge(suffixLink);
            }
            return false;
        }

        private void UpdateSuffixNode(Node node, Node suffixNode)
        {
            if (node != null && node != _root)
            {
                node.SuffixNode = suffixNode;
            }
        }

        public CommonSubstring FindLongestRepeatition()
        {
            var visited = new Stack<Node>();
            visited.Push(RootNode);
            int maxLength = 0;
            Edge bestCandidate = null;
            while (visited.Count > 0)
            {
                var current = visited.Pop();
                var edges = current.GetEdges();

                foreach (var edge in edges)
                {
                    if (edge.EndIndex + 1 < _text.Length && edge.GetSpan() > maxLength)
                    {
                        bestCandidate = edge;
                        maxLength = edge.GetSpan();
                    }
                    visited.Push(edge.EndNode);
                }
            }
            if (bestCandidate == null) return null;
            var repeatitions = bestCandidate.EndNode.GetEdges();
            var commonSubstring = new CommonSubstring
                {
                    Length = maxLength + 1,
                    TextIndices = new int[repeatitions.Length],
                    BeginIndices = new int[repeatitions.Length],
                    EndIndices = new int[repeatitions.Length]
                };

            int i = 0;
            foreach (Edge edge in repeatitions)
            {
                commonSubstring.BeginIndices[i] = edge.BeginIndex - commonSubstring.Length;
                commonSubstring.EndIndices[i] = edge.EndIndex - commonSubstring.Length;
                i++;
            }
            return commonSubstring;
        }

        public bool Contains(char[] str)
        {
            return IndexOf(str) >= 0;
        }

        public int IndexOf(char[] str)
        {
            if (str.Length == 0)
                return -1;

            int index = -1;
            Node node = _root;

            int i = 0;
            while (i < str.Length)
            {
                if ((node == null) || (i == _text.Length))
                    return -1;

                Edge edge = node.FindEdge(str[i]);
                if (edge == null)
                    return -1;

                index = edge.BeginIndex - i;
                i++;

                for (int j = edge.BeginIndex + 1; j <= edge.EndIndex; j++)
                {
                    if (i == str.Length)
                        break;
                    if (_text[j] != str[i])
                        return -1;
                    i++;
                }
                node = edge.EndNode;
            }
            return index;
        }
    }
}